package com.example.sort;

public class EightQueenProblem {
    // 定义一个数组，用于保存皇后的位置
    private int[] queens = new int[8];

    public static void main(String[] args) {
        EightQueenProblem eightQueenProblem = new EightQueenProblem();
        eightQueenProblem.solve(0);
    }

    // 解决八皇后问题的方法，参数 row 表示当前要放置的行
    public void solve(int row) {
        // 如果所有行都处理完毕，输出结果
        if (row == 8) {
            printSolution();
            return;
        }
        // 尝试将皇后放在当前行的每一列
        for (int column = 0; column < 8; column++) {
            queens[row] = column;
            // 如果当前位置合法，则继续放置下一行的皇后
            if (isSafe(row)) {
                solve(row + 1);
            }
        }
    }

    // 判断当前位置是否合法的方法
    private boolean isSafe(int row) {
        // 检查当前皇后与之前放置的皇后是否在同一列或对角线上
        for (int i = 0; i < row; i++) {
            // 检查列是否相同
            if (queens[i] == queens[row]) {
                return false;
            }
            // 检查对角线是否相交
            if (Math.abs(queens[i] - queens[row]) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    // 输出解决方案的方法
    private void printSolution() {
        System.out.println("八皇后问题的解决方案：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}